function qsort(array)
    local table_length = table.getn(array)
    if table_length == 0 then
	return {}
    elseif table_length == 1 then
	return array
    else
	local pivot = array[1]
	local left_part = {}
	local right_part = {}
	for x=2, table_length do
	    val = array[x]
	    if val < pivot then
		table.insert(left_part, val)
	    else
		table.insert(right_part, val)
	    end
	end
	local sorted_left = qsort(left_part)
	local sorted_right = qsort(right_part)
	table_length = table.getn(sorted_left) + 1
	table.insert(sorted_left, table_length, pivot)
	for i, v in ipairs(sorted_right) do
	    table.insert(sorted_left, i+table_length, v)
	end
	return sorted_left
    end
end

function mergesort(left, right)
    sorted = {}
    left_index = 1
    right_index = 1
    left_size = table.getn(left)
    right_size = table.getn(right)
    while (left_size+1) > left_index and (right_size+1) > right_index do
	if left[left_index] < right[right_index] then
	    table.insert(sorted, left[left_index])
	    left_index = left_index + 1
	else
	    table.insert(sorted, right[right_index])
	    right_index = right_index + 1
	end
    end
    if left_index == (left_size+1) then
        for x=right_index, right_size do
            table.insert(sorted, right[x])
        end
    else
        for x=left_index, left_size do
            table.insert(sorted, left[x])
        end
    end
    return sorted
end

int_count = tonumber(arg[1])
random_ints = {}
for x=1, int_count do
    table.insert(random_ints, int_count + 1 - x)
end

left_half = {}
right_half = {}
for x=1, (math.ceil(int_count/2)) do
    table.insert(left_half, random_ints[x])
end
for x=(math.ceil(int_count/2)+1), int_count do
    table.insert(right_half, random_ints[x])
end

sorted_left = qsort(left_half)
sorted_right = qsort(right_half)

sorted = mergesort(sorted_left, sorted_right)
print("[" .. table.concat(sorted, ", ") .. "]")
